【数据结构与算法】 二叉树的四种遍历方式
二叉树的遍历
对于一个图，有两种遍历方式：深度优先遍历（DFS）和广度优先遍历（BFS)。
作为一类特殊的有向无环图，二叉树的BFS体现为层序遍历，而因为子节点是有序的，根据访问根节点的顺序，二叉树的DFS体现为三种方式，即先序遍历、中序遍历和后序遍历。
层序遍历一般使用队列辅助的非递归方法，而先序遍历、中序遍历和后序遍历这三种则既可以递归实现，也可以使用辅助栈实现，甚至还有高级的 Morris 遍历实现。
熟练地掌握这四种遍历不同的实现方法，在具体场景中选择合适的遍历方式和实现方法，写出模板，然后根据要求调整代码。
参考资料
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 namespace LANG！
相关推荐
评论